home *** CD-ROM | disk | FTP | other *** search
/ BCI NET 2 / BCI NET 2.iso / archives / programming / source / graphicgems4.lha / GemsIV / graph_layout / layout.C < prev    next >
Encoding:
C/C++ Source or Header  |  1995-02-06  |  9.2 KB  |  292 lines
  1. /****************************************************************************
  2. ** DYNAMIC LAYOUT ALGORITHM OF GENERAL GRAPHS
  3. **
  4. ** Author: dr. Szirmay-Kalos Laszlo (szirmay@fsz.bme.hu)
  5. **       Technical University of Budapest, Hungary
  6. *****************************************************************************/
  7.  
  8. #ifdef MSWINDOWS
  9. #include "graph.hxx"
  10. #else
  11. #include "graph.hxx"
  12. #endif
  13.  
  14. /*
  15. *    CONSTANTS
  16. */
  17. const double TIME_STEP = 0.1;         // time step of diff equ
  18.  
  19. const double MAX_FORCE = 500.0;         // force shows instability
  20. const double MIN_FORCE = 2.0;         // force cosidered as 0
  21. const double MAX_TIME_SCALE = 10.0;  // scale of max time of solution
  22.  
  23. const double MINFRICTION = 0.6;         // friction boundaries
  24. const double MAXFRICTION = 0.9;
  25. const double MINIINERTIA = 0.1;         // inverse inertia boundaries
  26. const double MAXIINERTIA = 0.4;
  27.  
  28. const double ZERO_DIST =    10.0;  // distance considered as 0
  29. const double WALL_OUT_DRIVE =    80.0;  // forces of the wall
  30. const double WALL_MARGIN_DRIVE = 1.0;
  31.  
  32. const double SCALECONSTRAINT = OVERWINDOW_X / 3.5 / MAXRELATION;
  33. const double MINCONSTRAINT = OVERWINDOW_X / 7.0;     // minimal constraint
  34.  
  35.  
  36. /****************************************************************************/
  37. /* DYNAMIC LAYOUT base on MECHANICAL SYSTEM ANALOGY                */
  38. /* IN  : The serial number of the maximal moveable node to be considered    */
  39. /* OUT : STOPPED  = All objects stopped                        */
  40. /*     INSTABLE = Instable, force goes to infinity                */
  41. /*     TOO_LONG = Too much time elapsed                    */
  42. /****************************************************************************/
  43. int Graph :: DynamicLayout( int maxsernum )
  44. /*--------------------------------------------------------------------------*/
  45. {
  46. /*
  47. *    LOCALS
  48. */
  49.     double constraint, friction, iinertia, dist;
  50.     vector drive;            // drive forces
  51.     vector direction;            // direction of drives
  52.     double MAX_TIME = MAX_TIME_SCALE * (nmovnode + nfixnode + 1);
  53. /*
  54. *    INIT SPEED OF MOVEABLE NODES TO 0
  55. */
  56.     if ( !FirstMoveNode() ) return STOPPED;
  57.     do    currnode -> Speed( ) = vector(0.0, 0.0); while ( NextNode( maxsernum ) );
  58. /*
  59. *    MAIN CYCLE OF TIME IN THE SOLUTION OF DIFF EQUATION
  60. */
  61.     for ( double t = 0.0 ; t < MAX_TIME ; t += TIME_STEP ) {
  62. /*
  63. *    INITIALIZE FORCE IN NODES TO 0
  64. */
  65.     FirstNode();
  66.     do currnode -> Force( ) = vector( 0.0, 0.0 ); while ( NextNode( maxsernum ) );
  67. /*
  68. *    CALCULATE FRICTION AND RESPONSE VALUES FROM t
  69. */
  70.     friction = MINFRICTION + (MAXFRICTION - MINFRICTION) * t / MAX_TIME;
  71.     iinertia = MAXIINERTIA - (MAXIINERTIA - MINIINERTIA) * t / MAX_TIME;
  72. /*
  73. *     CALCULATE DRIVE FORCE BETWEEN EACH PAIR OF NODES
  74. */
  75.     FirstNode();
  76.     do {
  77.       relatenode = currnode -> GetNext();
  78.       while ( relatenode != NULL && relatenode -> GetSerNum() <= maxsernum ) {
  79.  
  80.         direction = currnode -> Position( ) - relatenode -> Position( );
  81.         dist  = direction.Size();
  82.         if ( dist < ZERO_DIST ) dist = ZERO_DIST;
  83. /*
  84. *    CALCULATE FORCE FROM THEIR RELATION
  85. */
  86.         switch( SearchRelation() ) {
  87.         case EMPTY_LIST:
  88.         case NOT_FOUND:
  89.         constraint = MINCONSTRAINT + MAXRELATION * SCALECONSTRAINT;
  90.         break;
  91.         case FOUND:
  92.         case FIRST_FOUND:
  93.         constraint = MINCONSTRAINT + (MAXRELATION - currelation->GetRelation()) * SCALECONSTRAINT;
  94.         break;
  95.         }
  96.         //    SET FORCE
  97.         drive = (constraint - dist) / dist * direction;
  98.         drive /= (double)(maxsernum + nfixnode);
  99.         currnode -> AddForce(drive);
  100.         relatenode -> AddForce(-drive);
  101.  
  102.         relatenode = relatenode -> GetNext();
  103.       }
  104.     } while ( NextNode( maxsernum ) );
  105. /*
  106. *    ADD ADDITIONAL FORCES AND DETERMINE MAXIMAL FORCE
  107. */
  108.     double max_force = 0.0;
  109.  
  110.     FirstMoveNode();
  111.     do {
  112. /*
  113. *   CALCULATE DRIVE FORCE OF BOUNDARIES AND ADD TO RELATION FORCES
  114. */
  115.        dist = currnode -> Position().X();
  116.        /*
  117.        *    FORCE OF LEFT WALL
  118.        */
  119.        if (dist < 0) {          // OUT LEFT
  120.          drive = vector( -dist * WALL_OUT_DRIVE + WALL_MARGIN * WALL_MARGIN_DRIVE, 0.0 );
  121.          currnode -> AddForce(drive);
  122.        } else if (dist < WALL_MARGIN) {    // IN LEFT MARGIN
  123.          drive = vector((WALL_MARGIN - dist) * WALL_MARGIN_DRIVE, 0.0);
  124.          currnode -> AddForce(drive);
  125.        }
  126.        /*
  127.        *    FORCE OF THE RIGHT WALL
  128.        */
  129.        dist = currnode -> Position().X() - OVERWINDOW_X;
  130.  
  131.        if (dist > 0) {          // OUT RIGHT
  132.          drive = vector( -dist * WALL_OUT_DRIVE + WALL_MARGIN * WALL_MARGIN_DRIVE, 0.0);
  133.          currnode -> AddForce(drive);
  134.        } else if (-dist < WALL_MARGIN) {    // IN RIGHT MARGIN
  135.          drive = vector((-WALL_MARGIN - dist) * WALL_MARGIN_DRIVE, 0.0);
  136.          currnode -> AddForce(drive);
  137.        }
  138.  
  139.        dist = currnode -> Position().Y();
  140.        /*
  141.        *    FORCE OF BOTTOM WALL
  142.        */
  143.        if (dist < 0) {          // OUT BOTTOM
  144.          drive = vector(0.0, -dist * WALL_OUT_DRIVE + WALL_MARGIN * WALL_MARGIN_DRIVE );
  145.          currnode -> AddForce(drive);
  146.        } else if (dist < WALL_MARGIN) {    // IN BOTTOM MARGIN
  147.          drive = vector(0.0, (WALL_MARGIN - dist) * WALL_MARGIN_DRIVE);
  148.          currnode -> AddForce(drive);
  149.        }
  150.        /*
  151.        *    FORCE OF THE TOP WALL
  152.        */
  153.        dist = currnode -> Position().Y() - OVERWINDOW_Y;
  154.  
  155.        if (dist > 0) {                      // OUT TOP
  156.          drive = vector( 0.0, -dist * WALL_OUT_DRIVE + WALL_MARGIN * WALL_MARGIN_DRIVE );
  157.          currnode -> AddForce(drive);
  158.        } else if (-dist < WALL_MARGIN) {            // IN TOP MARGIN
  159.          drive = vector(0.0, (-WALL_MARGIN - dist) * WALL_MARGIN_DRIVE);
  160.          currnode -> AddForce(drive);
  161.        }
  162. /*
  163. *    MOVE NODE BY FORCE
  164. */
  165.         vector old_speed = currnode -> Speed( );
  166.         currnode -> Speed( ) = (1.0 - friction) * old_speed + iinertia * currnode -> Force( );
  167.         currnode -> Position( ) += 0.5 * (old_speed + currnode -> Speed( ) );
  168.  
  169. /*
  170. *    CALCULATE MAXIMUM FORCE
  171. */
  172.         double abs_force = currnode -> Force().Size( );
  173.         if ( abs_force > max_force) max_force = abs_force;
  174.  
  175.     } while ( NextNode( maxsernum ) );
  176. /*
  177. *    STOP CALCULATION IF
  178. */
  179.     if ( max_force < MIN_FORCE ) return STOPPED;  // All objects stopped
  180.     if ( max_force > MAX_FORCE ) return INSTABLE; // Instable, force goes to infinity
  181.     }
  182.     return TOO_LONG; // Too much time elapsed
  183. }
  184.  
  185. /************************************************************************/
  186. /*    INITIAL PLACEMENT ALGORITHM                    */
  187. /* OUT : STOPPED  = All objects stopped                    */
  188. /*     INSTABLE = Instable, force goes to infinity            */
  189. /*     TOO_LONG = Too much time elapsed                */
  190. /************************************************************************/
  191. int Graph :: Placement( )
  192. /*----------------------------------------------------------------------*/
  193. {
  194.     vector    candidate;        // candidate position
  195.     vector    relate_cent;        // center related objects
  196.     vector    notrel_cent;        // center of related object
  197.     vector    center( OVERWINDOW_X / 2, OVERWINDOW_Y / 2 );
  198.     int        nrel;            // number of related objects
  199.     int        nnotrel;        // displayed nodes
  200.     double    perturb_x = OVERWINDOW_X / (double)RAND_MAX ;
  201.     double    perturb_y = OVERWINDOW_Y / (double)RAND_MAX ;
  202.  
  203. /*
  204. *    SKIP FIXED NODES
  205. */
  206.     if ( !FirstMoveNode() ) return STOPPED;
  207. /*
  208. *     MAIN CYCLE OF INTRODUCING MOVABLE NODES STEP-BY-STEP
  209. */
  210.     for( int inode = 1; ; inode++ ) {
  211. /*
  212. *    CALCULATE THE CENTER OF GRAVITY OF ALREADY INTRODUCED NODES
  213. *    relate_cent IS FOR RELATED NODES
  214. *    notrel_cent IS FOR NON_RELATED NODES
  215. */
  216.     relate_cent = vector(0.0, 0.0);
  217.     notrel_cent = vector(0.0, 0.0);
  218.     nrel = 0;
  219.     nnotrel = 0;            // displayed nodes
  220.     relatenode = currnode;
  221.  
  222.     for( FirstNode(); currnode != relatenode; NextNode() ) {
  223.         switch ( SearchRelation() ) {
  224.         case EMPTY_LIST:
  225.         case NOT_FOUND:
  226.             notrel_cent += currnode -> Position();
  227.             nnotrel++;
  228.             break;
  229.         case FIRST_FOUND:
  230.         case FOUND:
  231.             relate_cent += currnode -> Position();
  232.             nrel++;
  233.             break;
  234.         }
  235.     }
  236.     if ( nrel != 0 )       relate_cent /= (double)nrel;
  237.     if ( nnotrel != 0 )    notrel_cent /= (double)nnotrel;
  238. /*
  239. *    IF THIS IS THE FIRST POINT -> PUT TO THE MIDDLE
  240. */
  241.     if (nrel == 0 && nnotrel == 0) candidate = center;
  242.     else
  243. /*
  244. *    IF NO NOT_RELATED NODE -> PUT TO THE CENTRE OF GRAVITY OF RELATED NODES
  245. */
  246.     if ( nnotrel == 0 ) candidate = relate_cent;
  247.     else
  248. /*
  249. *    IF NO RELATED NODE -> PUT TO THE MIRROR OF THE nrel_cent ON THE CENTRE
  250. */
  251.     if ( nrel == 0 )  candidate = 2.0 * center - notrel_cent;
  252.     else
  253. /*
  254. *    BOTH TYPE OF NODES EXIST ->
  255. *    CALCULATE THE CANDIDATE POINT AS THE HALF MIRROR OF notrel_cent TO relate_cent
  256. */
  257.         candidate = 2.0 * relate_cent - 1.0 * notrel_cent;
  258. /*
  259. *    PERTURBATE RANDOMLY
  260. */
  261.     candidate += vector( perturb_x / (double)(nfixnode + inode + 5) *
  262.                  (double)( rand() - RAND_MAX / 2),
  263.                  perturb_y / (double)(nfixnode + inode + 5) *
  264.                  (double)( rand() - RAND_MAX / 2 ));
  265. /*
  266. *    DECIDE IF IT IS OUTSIDE -> FIND THE NEAREST INSIDE POINT
  267. */
  268.     if ( candidate.X() < WALL_MARGIN)
  269.         candidate = vector( 2.0 * WALL_MARGIN, candidate.Y() );
  270.     if ( candidate.X() > OVERWINDOW_X - WALL_MARGIN)
  271.         candidate = vector(OVERWINDOW_X - 2.0 * WALL_MARGIN, candidate.Y());
  272.  
  273.     if ( candidate.Y() < WALL_MARGIN)
  274.         candidate = vector( candidate.X(), 2.0 * WALL_MARGIN );
  275.     if ( candidate.Y() > OVERWINDOW_Y - WALL_MARGIN)
  276.         candidate = vector(candidate.X(), OVERWINDOW_Y - 2.0 * WALL_MARGIN );
  277.  
  278. /*
  279. *    SET POSITION OF THE NEW NODE
  280. */
  281.     relatenode -> Position( ) = candidate;
  282. /*
  283. *    ARRANGE ALREADY DEFINED NODES BY DYNAMIC LAYOUT -> IGNORE EDGE CONSTRAINTS
  284. */
  285.     NodeElem * oldcurrnode = currnode;
  286.     char ret = DynamicLayout( inode );
  287.     currnode = oldcurrnode;
  288.  
  289.     if ( ret != STOPPED || !NextNode() ) return ret;
  290.     }
  291. }
  292.